using System;
using System.Collections.Generic;

// 二叉树测试类
public class BinaryTreeTest
{
    public static void RunTest()
    {
        TreeNode root = new(1);
        root.left = new(2);
        root.right = new(3);
        root.left.left = new(4);
        root.left.right = new(5);
        root.right.left = new(6);
        root.right.right = new(7);

        Console.WriteLine("========== 二叉树遍历测试 ==========");
        Console.WriteLine("\n层序遍历:");
        root.EasyBFS(root);

        Console.WriteLine("\n按 Enter 键继续...");
        Console.ReadLine();

        Console.WriteLine("\n带层数的层序遍历:");
        root.EasyBFSWithLevel1(root);

        Console.WriteLine("\n按 Enter 键继续...");
        Console.ReadLine();

        Console.WriteLine("\n分层的层序遍历:");
        root.MiddleBFS(root);
    }
}

// 基本的二叉树节点
public class TreeNode {
    public int val;
    public TreeNode left, right;

    public TreeNode(int val){
        this.val = val;
        this.left = null;
        this.right = null;
    }
    //二叉树遍历框架
    public void Traverse(TreeNode root){
        if(root == null){
            return;
        }
        //前序位置
        Traverse(root.left);
        //中序位置  
        Traverse(root.right);
        //后序位置
    }

    /// <summary>
    /// 简单层序遍历
    /// </summary>
    public void EasyBFS(TreeNode root){
        if(root == null){
            return;
        }
        Queue<TreeNode> queue = new();
        //将根节点入队
        queue.Enqueue(root);
        while(queue.Count > 0){ 
            TreeNode curNode = queue.Dequeue();

            //这里可以访问当前 节点的信息
            Console.WriteLine(curNode.val);

            if(curNode.left != null){
                queue.Enqueue(curNode.left);
            }
            if(curNode.right != null){
                queue.Enqueue(curNode.right);
            }
        }
    }

    /// <summary>
    /// 简单层序遍历 - 带层数记录
    /// </summary>
    public void EasyBFSWithLevel1(TreeNode root){
        if(root == null){
            return;
        }
        Queue<(TreeNode node, int level)> queue = new();
        //将根节点入队，层数为0
        queue.Enqueue((root, 0));
        while(queue.Count > 0){ 
            var (curNode, level) = queue.Dequeue();

            //这里可以访问当前 节点的信息
            Console.WriteLine(curNode.val + " 当前层数: " + level);

            if(curNode.left != null){
                queue.Enqueue((curNode.left, level + 1));
            }
            if(curNode.right != null){
                queue.Enqueue((curNode.right, level + 1));
            }
        }
    }


    /// <summary>
    /// 中等层序遍历 也是记录层数
    /// </summary>
    public void MiddleBFS(TreeNode root){
        if(root == null){
            return;
        }
        Queue<TreeNode> queue = new();
        //记录层数
        int Death= 0;
        int size = 0;
        int i = 0;
        //将根节点入队
        queue.Enqueue(root);
        while(queue.Count > 0){ 
            size = queue.Count;
            for(i = 0; i < size; i++){
                TreeNode curNode = queue.Dequeue();

                //这里可以访问当前 节点的信息
                Console.WriteLine(curNode.val + "当前节点处于的层数" + Death);
                
                if(curNode.left != null){
                    queue.Enqueue(curNode.left);
                }
                if(curNode.right != null){
                    queue.Enqueue(curNode.right);
                }
            }
            Death++;
        }
    }

}
